package com.ai.zuochengyun.phase01.class07;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 打印所有子序列
 */
public class Code03_PrintAllSubSequence {

    public static void main(String[] args) {
        List<String> subs = subs("accccc");
        Set<String> subs2 = subsNoRepeat("accccc");
        for (String sub : subs) {
            System.out.println(sub);
        }
        System.out.println("=================");
        for (String sub : subs2) {
            System.out.println(sub);
        }
    }

    public static List<String> subs(String s) {
        if (s == null || s.isEmpty()) {
            return new ArrayList<>();
        }
        // 之前已经选好的子序列
        String path = "";
        List<String> ans = new ArrayList<>();
        // 将字符串从0位置开始的所有子序列都加入到ans列表中
        process1(s, 0, path, ans);
        return ans;
    }

    /**
     * 递归方法
     * @param s 字符串
     * @param index 来到的下标
     * @param path 之前决定path
     * @param ans 序列集
     */
    private static void process1(String s, int index, String path, List<String> ans) {
        // 确定base case，当下标来到数组末尾时，结束
        if (index == s.length()) {
            ans.add(path);
            return;
        }

        // 对于每个位置的字符，有两种选择，一种是要，一种是不要
        // 对于不要的，那么不会加入path中，只是index增加
        process1(s, index+1, path, ans);

        // 对于要的，那么需要将当前字符加入path中，并且index增加
        process1(s, index+1, path+s.charAt(index), ans);
    }


    public static Set<String> subsNoRepeat(String s) {
        if (s == null || s.isEmpty()) {
            return new HashSet<>();
        }
        // 子序列
        String path = "";
        Set<String> ans = new HashSet<>();
        // 将字符串从0位置开始的所有子序列都加入到ans列表中
        process2(s, 0, path, ans);
        return ans;
    }

    /**
     * 递归方法
     * @param s 字符串
     * @param index 来到的下标
     * @param path 之前决定path
     * @param ans 序列集
     */
    private static void process2(String s, int index, String path, Set<String> ans) {
        // 确定base case，当下标来到数组末尾时，结束
        if (index == s.length()) {
            ans.add(path);
            return;
        }

        // 对于每个位置的字符，有两种选择，一种是要，一种是不要
        // 对于不要的，那么不会加入path中，只是index增加
        process2(s, index+1, path, ans);

        // 对于要的，那么需要将当前字符加入path中，并且index增加
        process2(s, index+1, path+s.charAt(index), ans);
    }
}
